package Fundamental.sort;

import java.util.Arrays;

public class InsertSort {

    public static void main(String[] args) {
        int[] a = { -1 , -2 ,  8 ,2 ,1 , 18 , 21 , 20 , 3 , 4};
        sort(a);
        System.out.println("swapCnt:" + swapCnt);
    }
    /**
     * 交换的次数
     * */
    private static int swapCnt = 0 ;
    public static void sort(int[] array){
        if(array.length <= 1){
            return;
        }
        int insertPosition = 0 ;
        int temp = 0 ;
        for (int i = 0; i < array.length; i++) {
            System.out.print("index:" + i + "====>");
            temp = array[i];
            insertPosition = findInsertPosition( array , i);
            moveAndInsert(array , insertPosition , i , temp );
            System.out.println(Arrays.toString(array));
        }
    }
    private static void swap(int[] array , int from , int to){
        swapCnt++;
        int temp = array[from];
        array[from] = array[to];
        array[to] = temp;
    }
    /**
     * 移动有序子集，给插入元素挪开地方，并将元素插入到相关的位置
     * */
    private static void moveAndInsert(int[] array, int insertPosition , int bound, int temp) {
        for (int i = bound; i > insertPosition  ; i--) {
              swap(array,i , i-1);
        }
        array[insertPosition] = temp ;
    }


    /**
     * 找到插入的位置
     * */
    private static int findInsertPosition(int[] array, int sortedBound) {
        for (int i = 0; i <= sortedBound; i++) {
            if(array[i] >= array[sortedBound]){
               return i ;
            }
        }
        return 0;
    }
}
